package src.CodeTopSecondPractice;

public class _215 {
    public int findKthLargest(int[] nums, int k) {
        heapSort(nums, k);
        return nums[nums.length - k];
    }

    public void heapSort(int[] nums, int k) {
        int temp = 0;
        for (int i = nums.length / 2 - 1 ; i >= 0 ; i--) {
            adjustHeap(nums, i, nums.length);
        }
        for (int j = nums.length - 1 ; j > 0 ; j--) {
            temp = nums[j];
            nums[j] = nums[0];
            nums[0] = temp;
            adjustHeap(nums, 0, j);
            if (j <= nums.length - k) {
                break;
            }
        }
    }

    public void adjustHeap(int[] nums, int i, int length) {
        int temp = nums[i];
        for (int k = i * 2 + 1 ; k < length ; k = k * 2 + 1) {
            if ((k + 1 < length) && nums[k] < nums[k + 1]) {
                k++;
            }
            if (nums[k] > temp) {
                nums[i] = nums[k];
                i = k;
            }else {
                break;
            }
        }
        nums[i] = temp;
    }
}
